1. Field of the Invention
The present invention relates to a multiplier and an arithmetic unit for calculating a sum of products, both of which are preferred to apply to a processor.
2. Description of the Related Art
General-purpose processors, in recent years, mostly tend to include a multiplier applying partial product generation with using a Booth""s algorithm and partial product addition by means of a carry save method. For relatively low cost processors for computers, there has been a great increase in the proportion of multiplication operations with a low degree of accuracy, in terms of approximately sixteen bits, mainly for signal processing, for example, image processing or the like, in addition to multiplication operations with a high degree of accuracy, in terms of thirty two or sixty four bits.
For the sake of reduction in the number of parts embodied in the calculation systems, recently, general-purpose processors are intended to carry out signal processing, which has conventionally been executed by a special-purpose processor, such as a DSP (Digital Signal Processor), etc. This means that the general-purpose processors need to have a function for executing a multiplication operation with a low degree of accuracy, in terms of sixteen bits. Because the large amount of data is handled in the signal processing, such as the image processing or the like, processors for performing such signal processing are required to have a function for executing a multiplication operation with a low degree of accuracy with high efficiency.
FIG. 8 illustrates the first example of a multiplier according to the conventional techniques. The multiplier shown in FIG. 8 comprises two multipliers 801a and 801b for performing multiplication operations with xe2x80x9csixteen bit accuracyxe2x80x9d, a sixty four bit adder 802, a sixty four bit register 803, selectors 804a, 804b, and an input selector 805 for sending data to an adder 804.
In this multiplier, thirty two bit data A including the sixteen most significant bits (a1) and the sixteen least significant bits (a2), and thirty two bit data B including the sixteen most significant bits (b1) and the sixteen least significant bits (b2) are given as input data. In a case of performing two multiplication operations with the xe2x80x9csixteen bit accuracyxe2x80x9d, in the multiplier, each set of the bits a1, a2, b1, and b2 is assumed as independent sixteen bit data. In this case, data including combinations of (a1, b1) and (a2, b2) are supplied to a corresponding one of the sixteen bit multipliers 801a and 801b, respectively, by controlling the selectors 804a and 804b. Now, each of the multipliers 801a and 801b concurrently outputs corresponding solution of (a1xc3x97b2) and (a2xc3x97b2) each as a multiplication result thereof.
In a case of performing a multiplication operation for calculating (Axc3x97B) with xe2x80x9cthirty two bit accuracyxe2x80x9d, the multiplier makes the multipliers 801a and 801b calculate (a1xc3x97b2) and (a2xc3x97b1) by controlling the selectors 804a and 804b. The adder 802 adds the calculation results and generates an intermediate result (a1xc3x97b2+a2xc3x97b1), and stores the generated result in the register 803. Now, the multiplier makes the multiplier 801a calculate (a1xc3x97b1), and makes the selector 805 output the value stored in the register 803. The adder 802 adds the output from the multiplier 801a and the output from the selector 805, and stores its resultant addition (a1xc3x97b2+a2xc3x97b1+a1xc3x97b1) in the register 803 as a new intermediate result. The adder 802 adds the new intermediate result with a multiplication result (a2xc3x97b2), and outputs the ultimate multiplication result (a1xc3x97b2+a2xc3x97b1+a1xc3x97b1+a2xc3x97b2).
The multiplier shown in FIG. 8 may carry out two multiplication operations with the xe2x80x9csixteen bit accuracyxe2x80x9d as well as a multiplication operation with xe2x80x9cthirty two bit accuracyxe2x80x9d. However, in the conventional multipliers, problematic performance is recognized in that multiplication operations are performed with low efficiency (especially, in the calculation time) with the xe2x80x9cthirty two bit accuracyxe2x80x9d, since the multipliers need to generate an intermediate result at least twice in the case of performing the multiplication operation with the xe2x80x9cthirty two bit accuracyxe2x80x9d.
FIG. 9 illustrates the second example of a conventional multiplier. The multiplier shown in FIG. 9 comprises a xe2x80x9cthirty two bitxe2x80x9d multiplier 901, and two xe2x80x9csixteen bitxe2x80x9d multipliers 902a and 902b. The conventional multiplier has such a structure so as to simultaneously execute two multiplication operations with the xe2x80x9csixteen bit accuracyxe2x80x9d, and execute a multiplication operation with the xe2x80x9cthirty two bit accuracyxe2x80x9d at high speed. However, in such a conventional multiplier, a problematic matter arises in that hardware becomes large in its scale, for the multiplier needs to include a multiplier with high accuracy, in addition to two multipliers with low accuracy.
As disclosed in Unexamined Japanese Patent Application KOKAI Publication No. H7-121354, a multiplier performs multiplication operations with high accuracy (double accuracy), multiplication operations with low accuracy (single accuracy), and calculations for obtaining inner products, and further multiplication operations for multiple prime numbers, by modifying a Booth""s algorithm. However, in this multiplier, a problematic matter arises in that no means for simultaneously executing multiplication operations with low accuracy is included, so that it is required a calculation time as the same as executing multiplication operations with high accuracy, for executing a set of multiplication operations with the low accuracy.
An object of the present invention is to provide a multiplier capable of executing multiplication operations with high accuracy at high speed, capable of executing a plurality of multiplication operations with low accuracy, and capable of attaining reduction of hardware scale.
Another object of the present invention is to provide an arithmetic unit, for calculating a sum of products, capable of executing a plurality of calculations with low accuracy, and capable of calculating a sum of products at high speed.
In order to achieve the above-described objects, according to the first aspect of the present invention, there is provided a multiplier for executing a multiplication operation using a Booth""s algorithm, comprising:
a Booth decoder which divides a multiplier (Y) into a plurality of partial bit rows and outputs the divided bit rows;
a first multiplier replacing circuit which replaces, with xe2x80x9c0xe2x80x9d, a value of a most significant bit (Y3) included in least significant half of bits of the multiplier (Y) in accordance with a first control signal (SIMD), so as to replace, with xe2x80x9c0xe2x80x9d, a predetermined bit included in the plurality of bit row;
a plurality of partial product generating circuits each of which is arranged in a manner corresponding to each corresponding one of the partial bit rows divided by the Booth decoder, and generates a partial product, represented in bits which are twice as many as a bit number of a multiplicand, of the multiplicand (X) and each corresponding partial bit row;
a first adder which adds bit rows including the least significant half of bits of the partial products generated by the plurality of partial product generating circuits;
a second adder which adds bit rows including most significant half of bits of the partial product generated by the plurality of partial product generating circuits, in consideration of one or more carry signals; and
a carry selecting circuit which selects either a bit row composed of xe2x80x9c0xe2x80x9d or one or more carry signals which the first adder outputs, in accordance with the first control signal (SIMD), and supplies, to the second adder, the selected data as one or more carry signals;
wherein each of the partial product generating circuit, which generates the partial product corresponding to the least significant half the bits included in the partial bit rows divided by the Booth decoder, and generates either partial product of full bits of the multiplicand (X) and each corresponding partial bit row or of the least significant half of bits of the multiplicand (X) and each corresponding bit row in accordance with a first select signal (SIMD), and
each of the partial product generating circuit, which generates the partial product corresponding to the most significant half the bits included in the partial bit rows divided by the Booth decoder, generates either partial product of full bits of the multiplicand (X) and each corresponding partial bit row or of the most significant half the bits of the multiplicand (X) and each corresponding bit row in accordance with the first control signal (SIMD).
Thus, the multiplier of the present invention can perform a multiplication operation with high accuracy and two multiplication operations with low accuracy. Besides, the multiplier of the present invention is not required to retain an intermediate result for performing the multiplication operation with high accuracy. Accordingly, the multiplier of the present invention parallelly executes two multiplication operations with low accuracy, and executes a multiplication operation at high speed with high accuracy, while attaining reduction of hardware in its scale.
In the above-described multiplier,
each of the partial product generating circuits which generates the partial product corresponding to the least significant half the bits included in the partial bit rows divided by the Booth decoder may include:
a first multiplicand replacing circuit which replaces each of the most significant half the bits of the multiplicand (X) with a value of a most significant bit included in the least significant half the bits in accordance with the first control signal (SIMD); and
partial product replacing circuits, each of which replaces, with xe2x80x9c0xe2x80x9d, each value of the most significant half the bits as a multiplication result in which the multiplicand (X) is multiplied by each corresponding partial bit row, in accordance with a first control signal (SIMD).
Each of the partial product generating circuits, which generates the partial product corresponding to the most significant half the bits included in the partial bit rows divided by the Booth decoder, may include a second multiplicand replacing circuit which replaces, with xe2x80x9c0xe2x80x9d, each value of the least significant half the bits of the multiplicand (X) in accordance with the first control signal (SIMD).
In such a structure,
in a case where the first control signal (SIMD) is to indicate either multiplication operation of obtaining, with high accuracy, a product of a value represented in full bits of the multiplier and a value represented in full bits of the multiplicand, or of obtaining, with low accuracy, a product of a value represented in the most significant half the bits of the multiplier and a value represented in the most significant half the bits of the multiplicand and a product of a value represented in the least significant half the bits of the multiplier and a value represented in the most significant half the bits of the multiplicand,
the first multiplier replacing circuit may replace, with xe2x80x9c0xe2x80x9d, a value of the most significant bit (Y3) included in one bit row of the least significant half the bits of the multiplier (Y), when the first control signal indicates a multiplication operation with low accuracy;
the first multiplicand replacing circuit may replace each of the most significant half the bits of the multiplicand (X) with a value of a most significant bit included in the least significant half the bits, when the first control signal indicates a multiplication operation with low accuracy;
each of the partial product replacing circuits may replace, with xe2x80x9c0xe2x80x9d, each value of the most significant half the bits of a multiplication result in which the multiplicand (X) is multiplied by each corresponding partial bit row, when the first control signal indicates a multiplication operation with low accuracy;
the second multiplicand replacing circuit may replace, with xe2x80x9c0xe2x80x9d, each value of the least significant half the bits of the multiplicand (X), when the first control signal indicates a multiplication operation with low accuracy; and
each of the carry selecting circuit selects and outputs the carry signals output by the first adder when a first control signal (SIMD) indicates a multiplication operation with high accuracy, and selects and outputs the bit row composed of xe2x80x9c0xe2x80x9d when the first control signal (SIMD) indicates a multiplication operation with low accuracy.
In the above-described multiplication circuit,
the first adder may include:
a first Wallace adder tree which calculates sum signals and carry signals of digits of the partial products generated by the plurality of partial product generating circuits; and
a first carry adder which adds the sum signals and the carry signals of the digits of the partial products which are calculated by the first Wallace adder tree, in a manner corresponding to each digit.
The second adder may comprise:
a second Wallace adder tree which calculates sum signals and carry signals of digits of the partial products generated by the plurality of partial product generating circuits, in consideration of the carry signals; and
a second carry adder which adds the sums and the carry signals of the digits of the partial products generated by the plurality of partial product generating circuits in a manner corresponding to each digit, in consideration of the carry signals.
The carry selecting circuit may comprise:
one or more selectors which select either xe2x80x9c0xe2x80x9d or a carry signal of one or more digits which the first Wallace adder tree outputs, and supply selected data to the second Wallace adder tree; and
a selector which selects either xe2x80x9c0xe2x80x9d or the carry signal which the first carry adder outputs, and supplies selected data to the second carry adder.
The above-described multiplier may further comprise a second multiplier replacing circuit which replaces, with xe2x80x9c0xe2x80x9d, a value of a predetermined bit of the multiplicand (X) in accordance with a second control signal (FUGOU-UMU) indicating whether to handle the multiplier (Y) and the multiplicand (X) as including a sign or not including any sign, so as to replace one or more values of one or more predetermined bits included in the plurality of partial bit rows, with xe2x80x9c0xe2x80x9d.
In this case, the plurality of partial product generating circuits may generate either partial product of the multiplicand which is handled as a value with including a sign or of the multiplicand which is handled as a value without including any sign.
In such a case, each of the partial product generating circuits which generates the partial product corresponding to the least significant half the bits included in the partial bit rows divided by the Booth decoder may comprise:
a third multiplicand replacing circuit which replaces each of the most significant half the bits of the multiplicand with a value of the most significant bit included in the least significant half the bits or with the bit row composed of xe2x80x9c0xe2x80x9d, in accordance with the first and second control signals; and
a first multiplicand expanding circuit which expands the multiplicand in its bit number by adding the multiplicand and the bit row composed of xe2x80x9c0xe2x80x9d or a value of the most significant bit of the multiplicand in accordance with the second control signal.
Each of the partial product generating circuits which generates the partial product corresponding to the most significant half the bits included in the partial bit rows divided by the Booth decoder may comprise:
a fourth multiplicand replacing circuit which replaces, with xe2x80x9c0xe2x80x9d, each value of the least significant half the bits of the multiplicand (X) in accordance with the first control signal; and
a second multiplicand expanding circuit which expands the multiplicand in its bit number by adding the multiplicand and the bit row composed of xe2x80x9c0xe2x80x9d or a value of the most significant bit of the multiplicand in accordance with a second control signal.
In the structure of the above,
the second multiplier replacing circuit may replace, with xe2x80x9c0xe2x80x9d, a value of a predetermined bit (Y3) of the multiplier (Y) when the second control signal (FUGOU) indicates to handle the multiplier and the multiplicand as including a sign; and
the third multiplicand replacing circuit may replace each of the most significant half the bits of the multiplicand with a value of the most significant bit included in the least significant half the bits, when the first control signal indicates a multiplication operation with low accuracy and the second control signal indicates to handle the multiplier and the multiplicand as including a sign, and may replace each of the most significant half the bits of the multiplicand with the bit row composed of xe2x80x9c0xe2x80x9d, when the first control signal indicates a multiplication operation with low accuracy and the second control signal indicates to handle the multiplier and the multiplicand as not including any sign;
the fourth multiplicand replacing circuit may replace, with xe2x80x9c0xe2x80x9d, each value of the least significant half the bits of the multiplicand (X), when the first control signal indicates a multiplication operation with low accuracy; and
the first and the second multiplicand expanding circuits may expand the multiplicand in its bit number by adding the multiplicand and the bit row including a value of the most significant bit of the multiplicand, when the second control signal indicates to handle the multiplier and the multiplicand as including a sign, and expand the multiplicand in its bit number by adding the multiplicand and the bit row composed of xe2x80x9c0xe2x80x9d, when the second control signal indicates to handle the multiplier and the multiplicand as not including any sign.
In order to achieve the above-described objects, according to the second aspect of the present invention, there is provided an arithmetic unit which obtains a sum of products and adds multiplication results executed with using a Booth""s algorithm, comprising:
a Booth decoder which divides a multiplier (Y) into a plurality of partial bit rows and outputs the divided partial bit rows;
a first multiplier replacing circuit which replaces, with xe2x80x9c0xe2x80x9d, a value of a most significant bit (Y3) included in the bit row of least significant half of bits of a multiplier (Y) in accordance with a first control signal (SIMD), so as to replace, with xe2x80x9c0xe2x80x9d, a predetermined bit included in the plurality of the partial bit rows;
a plurality of partial product generating circuits, each of which is arranged in a manner corresponding to each corresponding one of the partial bit row divided by the Booth decoder, generates a partial product, represented in bits which are twice as many as a bit number of the multiplicand (X), of a multiplicand (X) and each partial bit row;
a first sum-of-product retaining circuit which retains a sum of products corresponding to the least significant half the bits of the partial products generated by the plurality of partial product generating circuits;
a second sum-of-product retaining circuit which retains a sum of products corresponding to most significant half the bits of the partial products generated by the plurality of partial product generating circuits;
a first adder which adds the bit rows of the least significant half the bits of the partial products generated by the plurality of partial product generating circuits, together with the sum of the products which is retained by the first sum-of-product retaining circuit;
a second adder which adds the bit rows of the most significant half the bits of the partial products generated by the plurality of partial product generating circuits, together with the sum of the products which is retained by the second sum-of-product retaining circuit, in consideration of a carry signal; and
carry selecting circuits each of which selects either a carry signal output by the first adder or a bit row composed of xe2x80x9c0xe2x80x9d in accordance with the first control signal (SIMD), and supplies the selected data as one or more carry signals to the second adders,
wherein each of the partial product generating circuits, which generates the partial product corresponding to the least significant half the bits of the partial bit rows divided by the Booth decoder, generates either partial product of each corresponding partial bit row and full bits of the multiplicand (X) or of each corresponding bit row and the least significant half the bits of the multiplicand (X) in accordance with a first select signal (SIMD), and
each of the partial product generating circuits, which generates the partial product corresponding to the most significant half the bits of the partial bit rows divided by the Booth decoder, generates either partial product of each corresponding partial bit row and full bits of the multiplicand (X) or of each corresponding partial bit row and the most significant half the bits of the multiplicand (X) in accordance with the first control signal (SIMD).
Such a arithmetic unit can perform an arithmetic operation for obtaining a sum of products with high accuracy, and two arithmetic operations for obtaining a sum of products with low accuracy. Further, it is not required to retain data representing an intermediate result but the so-far-obtained sum of products, for performing a calculation for obtaining the sum of products with high accuracy. Therefore, the arithmetic unit for calculating the sum of products can simultaneously execute two arithmetic operations for obtaining a sum of products with low accuracy, and can execute an arithmetic operation for obtaining a sum of products with high accuracy at high speed.
In the above-described arithmetic unit for obtaining a sum of products,
each of the partial product generating circuits, which generates the partial product corresponding to the least significant half the bits included in the partial bit rows divided by the Booth decoder, may include
a first multiplicand replacing circuit which replaces each of the most significant half the bits of the multiplicand (X) with a value of a most significant bit included in the least significant half the bits, in accordance with the first control signal (SIMD),
partial product replacing circuits which replaces, with xe2x80x9c0xe2x80x9d, each value of the most significant half the bits representing a multiplication result in which the multiplicand (X) is multiplied by each corresponding bit row in accordance with the first control signal (SIMD).
Each of the partial product generating circuits, which generates the partial product corresponding to the most significant half the bits included in the partial bit rows divided by the Booth decoder, may include
a second multiplicand replacing circuit which replaces, with xe2x80x9c0xe2x80x9d, each value of the least significant half the bits of the multiplicand (X) in accordance with the first control signal (SIMD).
In such a structure,
in a case where the first control signal (SIMD) is to indicate either multiplication operation of calculating, with high accuracy, a product of a value represented in full bits of the multiplier and a value represented in full bits of the multiplicand, or of calculating, with low accuracy, a product of a value represented in the most significant half the bits of the multiplier and a value represented in the most significant half the bits of the multiplicand and a product of a value represented in the least significant half the bits of the multiplier and a value represented in the most significant half the bits of the multiplicand;
the first multiplier replacing circuit may select and output xe2x80x9c0xe2x80x9d, when the first control signal indicates a multiplication operation with low accuracy;
the first multiplier replacing circuit may replace each of the most significant half the bits of the multiplier (X) with a value of a most significant bit included in the least significant half the bits, when the first control signal indicates a multiplication operation with low accuracy;
each of the partial product replacing circuits may replace, with xe2x80x9c0xe2x80x9d, each value of the most significant half the bits of a multiplication result in which the multiplicand (X) is multiplied by each corresponding partial bit row, when the first control signal indicates a multiplication operation with low accuracy;
the second multiplicand replacing circuit may replace, with xe2x80x9c0xe2x80x9d, the least significant half the bits of the multiplicand (X), when the first control signal indicates a multiplication operation with low accuracy; and
the carry selecting circuit may select and output carry signals which the first adder outputs, when the first control signal (SIMD) indicates a multiplication operation with high accuracy, and may select and output the bit row composed of xe2x80x9c0xe2x80x9d, when the first control signal (SIMD) indicates a multiplication operation with low accuracy.
The above-described arithmetic unit for obtaining a sum of products may further comprise second multiplier replacing circuits each of which replaces, with xe2x80x9c0xe2x80x9d, a value of a predetermined bit of the multiplier (Y), in accordance with a second control signal (FUGOU-UMU) indicating whether to handle the multiplier (Y) and multiplicand (X) as including or not including a sign, so as to replace a value of a predetermined bit included in the plurality of partial bit rows, with xe2x80x9c0xe2x80x9d.
In this case, each of the plurality of partial product generating circuits may generate either partial product of a multiplicand which is handled as including a sign or of a multiplicand which is handled as not including any sign, in accordance with the second control signal.
In the above-described case,
each of the partial product generating circuits, which generates the partial product corresponding to the least significant half the bits included in the partial bit rows divided by the Booth decoder, may include
a third multiplicand replacing circuit which replaces each of the most significant half the bits of the multiplicand with the bit row composed of xe2x80x9c0xe2x80x9d or a value of a most significant bit included in the least significant half the bits, and
a first multiplicand expanding circuit which expands the multiplicand in its bit number by adding the multiplicand and the bit row composed of xe2x80x9c0xe2x80x9d or a value of a most significant bit of the multiplicand in accordance with the second control signal.
Each of the partial product generating circuit, which generates the partial product corresponding to the most significant half the bits included in the partial bit rows divided by the Booth decoder may include
a fourth multiplicand replacing circuit which replaces, with xe2x80x9c0xe2x80x9d, each value of the least significant half the bits of the multiplicand (X) in accordance with the first control signal, and
a second multiplicand expanding circuit which expands the multiplicand in its bit number by adding the multiplicand and the bit row composed of xe2x80x9c0xe2x80x9d or including a value of a most significant bit of the multiplicand in accordance with the second control signal.
In the structure of the above,
the second multiplicand replacing circuits may replace, with xe2x80x9c0xe2x80x9d, a value of a predetermined bit (Y3) of the multiplier (Y), when the second control signal (FUGOU) indicates to handle the multiplier and the multiplicand as including a sign;
the third multiplicand replacing circuit
may replace each of the most significant half the bits of the multiplicand with a value of a most significant bits included in the least significant half the bits, when the first control signal indicates a multiplication operation with low accuracy and the second control signal indicates to handle the multiplier and the multiplicand as including a sign, and
may replace each of the most significant half the bits of the multiplicand with the bit row composed of xe2x80x9c0xe2x80x9d, when the first control signal indicates a multiplication operation with low accuracy and the second control signal indicates to handle the multiplier and the multiplicand as not including any sign;
the fourth multiplicand replacing circuit may replace, with xe2x80x9c0xe2x80x9d, each value of the least significant half the bits of the multiplicand (X), when the first control signal indicates a multiplication operation with low accuracy; and
each of the first and second multiplicand expanding circuits
may expand the multiplicand in its bit number by adding the multiplicand and the bit row including a value of the most significant bit of the multiplicand, when the second control signal indicates to handle the multiplier and the multiplicand as including a sign, and
may expand the multiplicand in its bit number by adding the multiplicand and the bit row composed of xe2x80x9c0xe2x80x9d, when the second control signal indicates to handle the multiplier and the multiplicand as not including any sign.
In order to achieve the above-described objects, according to the third aspect of the present invention, there is provided a multiplication method for carrying out a multiplication operation using a Booth""s algorithm, comprising:
dividing a multiplier (Y) into a plurality of partial bit rows;
replacing, with xe2x80x9c0xe2x80x9d, a value of a most significant bit (Y3) included in least significant half of bits of the multiplier (Y) in accordance with a first control signal (SIMD), so as to replace a predetermined bit included in the plurality of partial bit rows;
parallelly generating partial products, represented in bits which are twice as many as a bit number of the multiplicand (X), of a multiplicand (X) and each corresponding one of the partial bit rows;
adding the bit rows of the least significant half the bits of the generated partial products;
selecting, as one or more carry signals, either a carry signal generated by an addition result of the bit rows of the least significant half the bits of the partial products or a bit row composed of xe2x80x9c0xe2x80x9d, in accordance with the first control signal (SIMD); and
adding the bit rows of most significant half the bits of each partial product, in consideration of a carry signal;
wherein the generating the partial products can be performed by
generating either partial product of full bits of the multiplicand (X) and each corresponding partial bit row or of the least significant half the bits of the multiplicand (X) and each corresponding bit row, in accordance with a first select signal (SIMD), in a case of generating a partial product of the multiplicand (X) and each partial bit row of the least significant half the bits, and
generating either partial product of full bits of the multiplicand (X) and each corresponding partial bit row or of the most significant half the bits of the multiplicand (X) and each corresponding bit row, in accordance with the first select signal (SIMD), in a case of generating a partial product of the multiplicand (X) and each corresponding partial bit row of the most significant half the bits.
In order to achieve the above-described objects, according to the fourth aspect of the present invention, there is provided a multiplication method for calculating a product of values represented by full bits of a multiplier and a multiplicand both capable of being divided into an identical number of blocks with each other, or a product of values each represented by a corresponding bit block, the method comprising:
dividing a multiplier into a plurality of partial bit rows;
replacing, with xe2x80x9c0xe2x80x9d, a value of a most significant bit included in each block of the multiplier in accordance with a first control signal, so as to replace a predetermined bit included in the plurality of partial bit rows with xe2x80x9c0xe2x80x9d;
parallelly generating a partial product, represented in bits which are twice as many as a bit number of a multiplicand, of the multiplicand (X) and each corresponding one of the partial bit rows;
dividing each of the generated partial products into number of predetermined blocks which is identical with number of the blocks of the multiplier and the multiplicand, and adding bits which belong to an identical block; and
selecting, in a case of adding the partial products represented in each block, either a carry signal or xe2x80x9c0xe2x80x9d, and inputting the selected data as a carry signal,
wherein the generating the partial products is performed by generating either partial product of full bits of the multiplicand and each corresponding bit row or of any block of the multiplicand and each corresponding bit row, in accordance with the first control signal.
By employing the multiplication method according to the fourth aspect of the present invention, two or more (arbitrary number of) arithmetic operations for obtaining a sum of products can parallelly be performed.
In order to achieve the above-described objects, according to the fifth aspect of the present invention, there is provided a method for calculating a sum of products and for adding a multiplication result executed by using a Booth""s algorithm, comprising:
dividing a multiplier (Y) into a plurality of partial bit rows;
replacing, with xe2x80x9c0xe2x80x9d, a value of a most significant bit (Y3) included in the partial bit row of least significant half of bits of a multiplier (Y) in accordance with a first control signal (SIMD), so as to replace a predetermined bit included in the plurality of partial bit rows;
parallelly generating partial products, represented in bits which are twice as many as a bit number of a multiplicand, of the multiplicand (X) and each corresponding one of the partial bit rows;
adding bit rows of the least significant half the bits of the generated partial products, together with so-far-obtained sums of products corresponding to the least significant half the bits;
selecting, as one or more carry signals, either a bit row composed of xe2x80x9c0xe2x80x9d or a carry signal which is generated by an addition result of the so-far-obtained sum of products corresponding to the bit row of the least significant half the bits of the partial products and corresponding to the least significant half the bits, in accordance with the first control signal (SIMD);
adding the bit row of most significant half the bits of the generated partial products, together with the so-far-obtained sum of the products corresponding to the most significant half the bits, in consideration of a carry signal; and
retaining a newly-calculated sum of the products, as the addition result of adding the least significant half and the most significant half the bits,
wherein the generating the partial products can be performed by
generating either partial product of full bits of the multiplicand (X) and each corresponding one of the partial bit rows or of the least significant half the bits of the multiplicand (X) and each corresponding one of the partial bit rows in accordance with a first select signal, in a case of generating a partial product of the multiplier (X) and the partial bit row of the least significant half the bits, and
generating either partial product of full bits of the multiplicand (X) and each corresponding one of the partial bit rows or of the most significant half the bits of the multiplicand (X) and each corresponding one of the bit rows in accordance with the first select signal, in a case of generating a partial product of the multiplier (X) and the partial bit row of the most significant half the bits.
In order to achieve the above-described objects, according to the sixth aspect of the present invention, there is provided a method for sequentially adding a product of values represented by full bits of a multiplier and a multiplicand both capable of being divided into an identical number of blocks with each other, or a product of values each represented by a corresponding bit block, the method comprising:
dividing the multiplier into a plurality of partial bit rows;
replacing, with xe2x80x9c0xe2x80x9d, a value of a most significant bit of each block of the multiplier in accordance with a first control signal, so as to replace a predetermined bit included in the plurality of partial bit rows;
parallelly generating partial products, each represented in bits which are twice as many as a bit number of the multiplicand (X), of the multiplicand (X) and each corresponding one of the partial bit rows;
dividing each of the generated partial products, into number of predetermined blocks which is identical with number of the blocks of the multiplier and the multiplicand, and adding the block of each of the partial product and a so-far-calculated sum of the products of the blocks, together with bits which belong to an identical block;
selecting either a carry signal or xe2x80x9c0xe2x80x9d in accordance with the first control signal, and inputting the selected data as one or more carry signals, in a case of adding the partial products of the blocks; and
retaining a newly-calculated sum of products, as an addition result of the blocks,
wherein the generating the partial products can be performed by generating either partial product of full bits of the multiplicand and each corresponding one of the partial bit rows or of any block of the multiplicand and a corresponding one of the bit rows, in accordance with the first control signal.
By employing the method for calculating the sum of products according to the sixth aspect of the present invention, two or more (arbitrary number of) calculations for obtaining a sum of products can parallelly be executed with low accuracy.